package com.dbh.alg.datastructure.stack;

import java.util.LinkedList;

/**
 * @author dongbanghui
 * @date 2025/5/28
 */
public class E03InfixToSuffix {

    /**
     *
     * 遇到非运算符入栈
     * 遇到 + - * /
     *              - 它的优先级比当前优先级高，入栈
     *              - 否则把把栈里优先级 >= 它元素都出栈，在入栈
     * 遍历完成栈里元素依次出栈
     * 带()
     *     - 左括号直接入栈，左括号优先级为0
     *     - 右括号就把栈里到左括号为止的所有运算符出栈
     */
    public static void main(String[] args) {
        System.out.println(infixToSuffix("a+b"));
        System.out.println(infixToSuffix("a-b"));
        System.out.println(infixToSuffix("a+b-c"));
        System.out.println(infixToSuffix("a+b*c"));
        System.out.println(infixToSuffix("a*b-c"));
    }

    public static int priority(char c) {
        switch (c) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            case '(':
                return 0;
            default:
                return -1; // 非运算符的优先级最低
        }
    }

    public static String infixToSuffix(String infix) {
        StringBuilder suffix = new StringBuilder();
        LinkedList<Character> stack = new LinkedList<>();
        for (char c : infix.toCharArray()) {
           switch (c) {
               case '+':
               case '-':
               case '*':
               case '/': {
                   if (stack.isEmpty()) {
                       stack.push(c);
                   } else {
                       if (priority(c) > priority(stack.peek())) {
                           // 如果当前运算符的优先级比栈顶元素高，直接入栈
                           stack.push(c);
                       } else {
                           // 否则把栈里优先级 >= 它的元素都出栈
                           while (!stack.isEmpty() && priority(c) <= priority(stack.peek())) {
                               suffix.append(stack.pop());
                           }
                           // 然后再把当前运算符入栈
                           stack.push(c);
                       }
                   }
                   break;
               }
               case '(': {
                     // 左括号直接入栈
                     stack.push(c);
                     break;
               }
               case ')': {
                     // 右括号就把栈里到左括号为止的所有运算符出栈
                     while (!stack.isEmpty() && stack.peek() != '(') {
                         suffix.append(stack.pop());
                     }
                     // 弹出左括号
                     if (!stack.isEmpty()) {
                         stack.pop();
                     }
                     break;
               }
               default: {
                     // 如果是数字或字母，直接添加到后缀表达式
                     suffix.append(c);
                     break;
               }

           }
        }
        // 遍历完成后，把栈里剩余的元素依次出栈
        while (!stack.isEmpty()) {
            suffix.append(stack.pop());
        }
        return suffix.toString();
    }

}
